package likou;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/11/29 16:56
 */
public class _1061 {
    public static void main(String[] args) {
        _1061 one = new _1061();
        System.out.println(one.smallestEquivalentString(
                "leetcode",
                "programs",
                "sourcecode"));
        System.out.println(one.smallestEquivalentString2(
                "leetcode",
                "programs",
                "sourcecode"));
    }

    // 并查集
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        char[] chars = new char[26];
        for (char a = 'a'; a <= 'z'; a++) {
            chars[a - 'a'] = a;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        for (int i = 0; i < cs1.length; i++) {
            char a = cs1[i], b = cs2[i];
            if (a < b) {
                while (chars[b - 'a'] != chars[a - 'a']) {
                    char father = chars[b - 'a'];
                    chars[b - 'a'] = chars[a - 'a'];
                    b = father;
                }
            } else {
                while (chars[b - 'a'] != chars[a - 'a']) {
                    char father = chars[a - 'a'];
                    chars[a - 'a'] = chars[b - 'a'];
                    a = father;
                }
            }
        }
        char[] baseChars = baseStr.toCharArray();
        char[] res = new char[baseChars.length];
        for (int i = 0; i < baseChars.length; i++) {
            res[i] = chars[baseChars[i] - 'a'];
        }
        return String.valueOf(res);
    }

    public char min(char a, char b) {
        return a > b ? b : a;
    }


    public String smallestEquivalentString2(String A, String B, String S) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        int len = A.length();
        char[] ch1 = A.toCharArray();
        char[] ch2 = B.toCharArray();
        for (int i = 0; i < len; i++) {
            int n1 = ch1[i] - 'a';
            int n2 = ch2[i] - 'a';
            union(parent, n1, n2);
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : S.toCharArray()) {
            int root = find(parent, ch - 'a');
            sb.append((char) (root + 'a'));
        }
        return sb.toString();
    }

    private int find(int[] parent, int index) {
        while (parent[index] != index) {
            index = parent[index];
        }
        return index;
    }

    private void union(int[] parent, int index1, int index2) {
        int xset = find(parent, index1);
        int yset = find(parent, index2);
        if (xset != yset) {
            if (xset < yset) {
                parent[yset] = xset;
            } else {
                parent[xset] = yset;
            }
        }
    }
}
